package features.advance.leetcode.array;

/**
 *  树状数组
 *
 * @author LIN
 * @date 2021-07-08
 */
public class BIT {
    private int[] tree;
    private int n;

    public BIT(int n) {
        this.n = n;
        this.tree = new int[n + 1];
    }

    public int lowbit(int x) {
        return x & (-x);
    }

    public int query(int x) {
        int ret = 0;
        while (x != 0) {
            ret += tree[x];
            x -= lowbit(x);
        }
        return ret;
    }

    public void update(int x) {
        while (x <= n) {
            ++tree[x];
            x += lowbit(x);
        }
    }

    public static int[] build(int[] nums){
        int n = nums.length+1;
        int[] res = new int[n];

        for (int i = 1; i < n; i++) {
            int x = i-(i & -i) +1;
            int y = 0;
            while(x <= i){
                res[i] += nums[x-1];
                x++;
            }
        }

        return res;
    }

    public static void main(String[] args) {
        int[] nums = {7,2,1,3,5,6,9};
        int[] build = build(nums);
        System.out.println(build);
    }

}
